// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 15:16
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import java.util.ArrayList;
import java.util.List;

public class IsSymmetricTree {
    // 判断一棵树是否是对称树

    // Definition for a binary tree node.
//    List<Integer> treeVal = new ArrayList<>();
//
//    public boolean isSymmetric(TreeNode root) {
//        // 讲给定的层次遍历的树按照先序遍历的结果保存，通过判断树的先序遍历结果就可以判断树是否是一棵对称树
//        // 对称树的节点个数是奇数
//        // 方法错误，无法单单通过中序遍历得到当前树是对称树
//        midOrder(root);
//        int i = 0, j = treeVal.size() - 1;
//        while (i != j) {
//            if (treeVal.get(i) != treeVal.get(j)) {
//                return false;
//            } else {
//                ++i;
//                --j;
//            }
//        }
//        return true;
//    }
//
//    // 中序遍历
//    private void midOrder(TreeNode root) {
//        if (root == null) {
//            treeVal.add(null);
//            return;
//        }
//        midOrder(root.left);
//        treeVal.add(root.val);
//        midOrder(root.right);
//    }

    // 通过根节点的左右子树的遍历顺序进行判断
    // 左子树-> 左->中->右
    // 右子树-> 右->中->左
//    List<Integer> L = new ArrayList<>(); // 记录左子树遍历顺序
//    List<Integer> R = new ArrayList<>(); // 记录右子树遍历顺序
//
//    public boolean isSymmetric(TreeNode root) {
//        if (root == null) {
//            return true;
//        }
//        lmr(root.left);
//        rml(root.right);
//        int ls = L.size();
//        int rs = R.size();
//        System.out.println(L);
//        System.out.println(R);
//
//
//        if (ls != rs) return false;
//        for (int i = 0; i < ls; i++) {
//            if (!L.get(i).equals(R.get(i))) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    private void lmr(TreeNode root) {
//        // 遍历根节点左子树顺序：中序遍历
//        if (root == null) {
//            L.add(null);
//            return;
//        }
//        lmr(root.left);
//        L.add(root.val);
//        lmr(root.right);
//    }
//
//    private void rml(TreeNode root) {
//        // 遍历根节点右子树顺序：逆序遍历
//        if (root == null) {
//            R.add(null);
//            return;
//        }
//        rml(root.right);
//        R.add(root.val);
//        rml(root.left);
//    }
//

    public boolean isSymmetric(TreeNode root) {
        // 树的同步遍历
        TreeNode p = root, q = root;
        return check(p, q);


    }

    private boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
